W9. Randomized Algorithms

1. Theory

1.1 Probability Basics

1.1.1 Sample Spaces and Events

To reason precisely about randomness, we need a formal vocabulary. The starting point is the sample space : the set of all possible outcomes of an experiment. For example, when tossing a coin three times, every sequence of heads (H) and tails (T) of length three is a possible outcome:

An event is any subset of the sample space. For instance, the event “exactly one tail” corresponds to:

This formal setup lets us reason carefully about what can happen and how likely each outcome is.

1.1.2 Axioms of Probability

A probability distribution is a function (where is the set of all subsets of ) that assigns a real number to every event and satisfies four axioms:

1. for any event — probabilities are non-negative.
2. — the probability of some outcome happening is 1.
3. for any two mutually exclusive events and (i.e., ).
4. for any finite or countably infinite sequence of pairwise mutually exclusive events.

is called the probability of event .

1.1.3 Basic Properties of Probability

The following properties follow directly from the axioms:

1. Proof: , so . Since , we get , hence .

2. where is the complement of .

   Proof: and , so .

3. Proof: We can split into the disjoint parts and . Then , so .

Example (coin tossing): Tossing a fair coin 3 times. Assuming all 8 outcomes are equally likely, each has probability . The event has probability .

1.2 Discrete Probability Distributions

A probability distribution is called discrete if it is defined on a finite or countably infinite sample space.

A special case is the uniform distribution: if is finite and every outcome has probability , the distribution is uniform. We say “we pick an element of uniformly at random.”

Examples:

• Rolling a fair six-sided die: with each outcome having probability . This is uniform.
• Sum of two fair dice: The sum ranges from 2 to 12, but not all sums are equally likely (e.g., a sum of 7 is more likely than 2). This is not uniform.
• Choosing a random student ID from a class of students: uniform (each ID equally likely).

1.3 Discrete Random Variables

A discrete random variable is a function that maps each outcome to a real number. For example, might represent the score in a game or the number of heads in a coin-toss experiment.

We define:

The function is called the probability mass function of .

1.3.1 Expected Value

The expected value (also called the expectation or mean) of a random variable is its probability-weighted average:

The expected value tells you what the “average” outcome would be if you repeated the experiment many times. For example, if you toss a fair coin and gain 1 point for heads and 0 for tails, the expected value is : on average, you gain half a point per toss.

Example: In a game where tossing two coins gives for HH, for HT or TH, and for TT:

1.3.2 Linearity of Expected Value

Expected value is a linear operator, meaning it satisfies:

This holds for any random variables and , not just independent ones. Linearity is the most-used property in probabilistic analysis, since it lets us split complex random variables into simple indicator variables.

If is a random variable and is any function, then is also a random variable and:

Note that in general — for instance, unless is constant.

When does fail to exist? The expected value is defined as a sum . This sum may diverge — grow without bound — in which case we say the expected value does not exist. A classic example is the St. Petersburg paradox: a game where you toss a fair coin repeatedly and win dollars if the first heads appears on toss . The expected winnings are — the expected value is infinite, so it “does not exist” in the usual finite sense. In algorithm analysis we always deal with finite, well-behaved distributions, so this issue does not arise in practice.

1.3.3 Independent Random Variables

Random variables and are independent if knowing the value of one gives no information about the value of the other. Formally, and are independent if and only if:

for all values and .

Example of dependent variables: Let (one coin toss). Define and . Then , but . So and are dependent: if you know (heads), you know for certain .

Multiplication rule for independent variables: If and are independent, then:

This is stronger than the additivity property and only holds when and are independent.

1.4 Indicator Random Variables

An indicator random variable (also called a Bernoulli random variable) for event is defined as:

Indicator variables are the main tool for converting probability statements into expected value calculations. The key lemma connects them:

Lemma (Cormen et al. 2022, Lemma 5.1). Let . Then .

Proof:

Why are indicator variables useful? They let us decompose complex random variables into sums of simple ones. If where each , then by linearity:

This is much easier to compute than reasoning directly about the distribution of .

Example (expected number of heads): When tossing a fair coin times, let and be the total number of heads. Then:

1.5 Probabilistic Analysis

Probabilistic analysis is the study of an algorithm’s behavior (especially its running time) using probability theory. Instead of asking “what is the worst possible running time?”, we ask “what is the expected running time averaged over all possible inputs?”

To apply probabilistic analysis, we need:

1. A known or assumed distribution of inputs.
2. Justified assumptions that the distribution is realistic for the use case.
3. Computation of the expected running time by averaging over all inputs under that distribution.

If we cannot justify a reasonable input distribution, probabilistic analysis may not be applicable.

1.5.1 The Hiring Problem

Imagine you are hiring an AI agent for a task. There are candidates, and you evaluate them one by one. Evaluating a candidate costs , and hiring (replacing the current agent) costs .

HIRE-ASSISTANT(n)
1  best = 0         // candidate 0 is a least-qualified dummy
2  for i = 1 to n
3      interview candidate i      // cost c_c
4      if candidate i is better than candidate best
5          best = i
6          hire candidate i       // cost c_h

Worst case: Candidates arrive in increasing order of quality — we hire every candidate. Total hiring cost: .

Best case: The best candidate arrives first — we hire only once. Total hiring cost: .

Probabilistic analysis: Assume candidates arrive in a uniformly random order (each of the permutations equally likely). Let . The -th candidate is hired exactly when they are the best among the first candidates. Since the order is random, any of the first candidates is equally likely to be the best, so:

The expected number of hires is:

This uses the fact that (the -th harmonic number), which grows as . So on average, we expect only expensive hires even though we evaluate all candidates.

1.6 Randomized Algorithms

The probabilistic analysis above required assuming a uniform random input. But what if candidates arrive in a specific (possibly adversarial) order? A randomized algorithm takes control of this uncertainty: instead of hoping the input is random, it makes the input random.

Definition: An algorithm is randomized if its behavior depends not only on the input but also on random choices made during execution (values from a random-number generator).

Randomized hiring: Before running HIRE-ASSISTANT, randomly shuffle the candidates using:

RANDOMLY-PERMUTE(A, n)
1  for i = 1 to n
2      swap A[i] with A[RANDOM(i, n)]

This produces a uniformly random permutation of the candidates. Now, regardless of the original input order, we can guarantee that the expected number of hires is — even against an adversary who chose the worst possible original order.

The key insight: probabilistic analysis relies on the input being random; randomized algorithms rely on the algorithm itself making random choices.

1.7 Randomized Quicksort

Quicksort is a classic divide-and-conquer sorting algorithm with the following properties:

1. It is a divide-and-conquer algorithm.
2. It runs in on average but in the worst case.
3. It is stable (equal elements maintain their relative order).
4. It has an efficient in-place implementation (no extra array needed).

The idea of the algorithm:

• Divide: Partition the array around a pivot element — put all elements smaller than the pivot before it, all larger elements after it.
• Conquer: A single-element subarray is already sorted.
• Combine: Concatenate the sorted subarrays with the pivot in the middle.

The worst case occurs when, e.g., the array is already sorted and we always pick the first or last element as pivot.

Randomized pivot selection avoids the worst case by choosing the pivot uniformly at random:

RANDOMIZED-PARTITION(A, p, r)
1  i = RANDOM(p, r)
2  exchange A[r] with A[i]
3  return PARTITION(A, p, r)

RANDOMIZED-QUICKSORT(A, p, r)
1  if p < r
2      q = RANDOMIZED-PARTITION(A, p, r)
3      RANDOMIZED-QUICKSORT(A, p, q - 1)
4      RANDOMIZED-QUICKSORT(A, q + 1, r)

1.7.1 Analysis of Randomized Quicksort

Lemma (Cormen et al. 2022, Lemma 7.1). If is the total number of comparisons in PARTITION across the entire execution, then the running time of QUICKSORT is .

To estimate the expected number of comparisons, let be the elements in sorted order. Define:

Then .

Key observation: Two elements and are compared if and only if one of them is the first pivot chosen from the set . This is because:

• If a pivot with is chosen before either or , they are separated into different subproblems and will never be compared.
• If or is chosen as pivot first (before any with ), they are compared directly.

Since each of the elements in is equally likely to be the first pivot from that set:

Therefore, the expected total number of comparisons is:

Summary of randomized quicksort:

• Works just like ordinary quicksort, but chooses the pivot randomly.
• Expected running time: on any input.
• Worst-case running time: still , but now it depends on the random number generator, not the input — an adversary cannot force the worst case by choosing a bad input.

1.8 Probabilistic Analysis of Bucket Sort

Bucket sort is a linear-time sorting algorithm that works under a specific assumption: the input values are uniformly distributed over some interval (typically ).

Algorithm:

1. Divide into equal-sized subintervals (“buckets”). Each subinterval has the same probability of receiving an element, since the input is uniform.
2. Assign each input element to the bucket corresponding to its subinterval: element goes to bucket (a cheap rounding operation).
3. Sort each bucket using insertion sort.
4. Concatenate the sorted buckets.

“Equal” here means equal in probability: each of the buckets covers an interval of length , and since the input is uniformly distributed, each element independently falls into any given bucket with probability .

Why does this work fast? If the input is uniformly distributed, each bucket expects to receive element on average, so the insertion sort within each bucket takes expected time.

1.8.1 Formal Analysis

Let be the number of elements in bucket . The running time of bucket sort is:

(The covers distributing elements into buckets; is the insertion sort cost for bucket .)

We want to compute .

Let , so .

Computing :

First sum: Since is a -valued indicator, (squaring 0 or 1 gives the same value). Therefore:

Second sum: For , the events “ falls into bucket ” and “ falls into bucket ” are independent — because and are independent uniform random variables (distinct input elements), so knowing where one falls gives no information about the other. By the multiplication rule for independent variables:

There are terms in the first sum and terms in the second sum, so:

Therefore, the expected total running time is:

Bucket sort runs in expected time when the input is uniformly distributed.

1.9 Randomly Built Binary Search Trees

A binary search tree (BST) is a binary tree satisfying the BST property: for every node , all keys in its left subtree are , and all keys in its right subtree are .

The shape (and thus efficiency) of a BST depends entirely on the order in which keys are inserted. When keys are inserted in a uniformly random order, the resulting tree is called a randomly built BST.

1.9.1 Two Different Notions of “Random BST”

It is important to distinguish two concepts:

1. Randomly chosen BST: Pick uniformly at random among all valid BST shapes on nodes. The number of such shapes is the -th Catalan number .
2. Randomly built BST: Start with an empty tree and insert a uniformly random permutation of distinct keys one by one. Each of the permutations is equally likely, but different permutations can produce the same tree shape, so this does not give a uniform distribution over tree shapes.

These two notions differ: for , there are 42 BST shapes (Catalan number ), but permutations. Permutations yielding tall, skewed trees are more likely under random insertion than under random shape selection.

Expected height of a randomly built BST: It is known (Cormen et al. 2022, §12.4) that the expected height of a randomly built BST on nodes is — the same asymptotic height as a perfectly balanced tree.

---

2. Definitions

• Sample space (): The set of all possible outcomes of a random experiment.
• Event: Any subset of the sample space .
• Probability distribution: A function satisfying the four axioms of probability; assigns a real number to every event.
• Discrete probability distribution: A probability distribution defined on a finite or countably infinite sample space.
• Uniform distribution: A discrete distribution on a finite sample space where every outcome has equal probability .
• Discrete random variable: A function mapping outcomes to real numbers on a finite or countably infinite sample space.
• Probability mass function: The function describing the probability distribution of a discrete random variable .
• Expected value (): The probability-weighted average of a random variable: .
• Linearity of expectation: The property , which holds for any random variables regardless of independence.
• Independent random variables: Random variables and such that for all .
• Indicator random variable (): A random variable that equals 1 if event occurs and 0 otherwise; its expected value equals .
• Probabilistic analysis: The analysis of an algorithm’s performance using probability theory, typically computing the expected running time over a distribution of inputs.
• Expected running time: The average running time of an algorithm computed by averaging over all possible inputs (or random choices) weighted by their probabilities.
• Randomized algorithm: An algorithm whose behavior depends on the input and on values produced by a random-number generator; it takes internal random choices rather than relying on the input being random.
• Random permutation: A permutation of a set chosen uniformly at random from all permutations; generated in place by the RANDOMLY-PERMUTE algorithm.
• Binary search tree (BST): A binary tree satisfying the BST property: keys in the left subtree of any node are that node’s key, and keys in the right subtree are that node’s key.
• Randomly built BST: A BST obtained by inserting distinct keys one by one in a uniformly random order; has expected height .
• Catalan number: The number of distinct binary tree shapes on nodes, given by .
• Pivot (quicksort): The element chosen to partition the array during quicksort; in randomized quicksort, chosen uniformly at random from the current subarray.
• Bucket sort: A sorting algorithm that distributes elements into equal-width buckets, sorts each bucket with insertion sort, and concatenates results; runs in expected time when input is uniformly distributed over .

---

3. Formulas

• Probability of complementary event:
• Inclusion-exclusion (two events):
• Expected value:
• Linearity of expectation: and
• Function of random variable:
• Independence (product rule): If and are independent, then
• Indicator variable lemma:
• Expected hires (hiring problem):
• Probability of comparison (quicksort):
• Expected comparisons (quicksort):
• Expected bucket size squared:
• Catalan number:
• Harmonic number:

---

4. Practice

4.1. Prove or Disprove Probability Identities (Problem Set 7, Task 1)

For each of the following equalities, either prove it using the axioms of probability and basic set identities, or provide a counterexample:

(a)

(b)

Click to see the solution

(a) :

This is false in general. We provide a counterexample.

Let with uniform distribution ( for each ). Let and .

Then:

Since , the equality fails.

The correct formula is: , which follows from with the two parts disjoint.

(b) :

This is false in general. We provide a counterexample.

Let with uniform distribution. Let , , .

• , so , thus .
• , so , thus .

This happens to be equal here. Let’s try , , :

• , so : .
• , so : .

Equal again. Let’s try , , :

• , so : .
• , so : .

Since , the equality fails.

Answer: (a) False — counterexample given above. (b) False — counterexample with , , in a 4-element uniform space.

4.2. Prove or Disprove Expectation Identities (Problem Set 7, Task 2)

For each of the following, either prove it or provide a counterexample. Assume all random variables take real values and all expected values exist.

(a)

(b) when and are independent.

(c)

(d)

Click to see the solution

(a) :

This is true. By linearity of expectation:

(b) when and are independent:

This is false in general, even with independence.

Counterexample: Let be independent copies of a variable taking values and each with probability .

Then:

• (by independence)

Since , the equality fails.

The correct statement would use Jensen’s inequality: since is concave, .

(c) :

This is false in general.

Counterexample: Let and be fair coin flips: is 0 or 1 with equal probability, and independently is 0 or 1 with equal probability.

• , so .
• only when (probability ); otherwise .
• .

Since , the equality fails. In general, .

(d) :

This is false in general.

Counterexample: Let take values and with equal probability .

• , so .
• when and when , so .

This happens to be equal here, but the equality is coincidental. Let take values 0 and 2 with equal probability:

• , so .
• .

The equality fails. In general, for nonlinear (Jensen’s inequality).

Answer: (a) True by linearity. (b) False — counterexample given. (c) False — counterexample given. (d) False — counterexample given.

4.3. Modular-Search Algorithm (Problem Set 7, Task 3)

Consider a Modular-Search algorithm that traverses an array using modular arithmetic: fix a constant step (e.g., ). Start at index 1, then visit indices (reducing modulo to stay in ). When , every index is visited exactly once over steps. The algorithm stops as soon as it finds an occurrence of the target value .

The array contains exactly copies of .

(a) Give a high-level description and pseudocode for Modular-Search.

(b) Analyze worst-case, best-case, and expected running time.

(c) Write pseudocode for Randomized-Search (using a random permutation instead of a fixed step).

(d) Derive the expected running time of Randomized-Search.

(e) Compare Modular-Search and Randomized-Search: when is the deterministic algorithm slow, and how does randomization help?

Click to see the solution

Key Concept: Modular-Search is a deterministic traversal; Randomized-Search uses a random permutation to avoid adversarial worst cases.

(a) Pseudocode for Modular-Search:

MODULAR-SEARCH(A, n, x, s)
1  idx = 1
2  for step = 1 to n
3      if A[idx] == x
4          return idx       // found x
5      idx = (idx - 1 + s) mod n + 1   // advance by s modulo n (1-indexed)
6  return NOT_FOUND

High-level description: We probe the array at positions (all modulo , 1-indexed). When , this visits all positions before repeating. We stop at the first position where .

(b) Running time analysis:

Worst case: An adversary places all copies of at the last positions that Modular-Search visits. Then we must examine positions before finding .

For : always . For constant : still .

Best case: The very first position visited contains a copy of . We stop after 1 step:

Expected case (assuming the positions of are uniformly random):

Since all positions are visited in a fixed but permuted order, and the positions of are uniformly random, by symmetry the expected position of the first occurrence of in the modular traversal order is (the expected minimum of a hypergeometric-like variable). More precisely, the expected number of steps until the first hit is:

(c) Pseudocode for Randomized-Search:

RANDOMIZED-SEARCH(A, n, x)
1  pi = RANDOMLY-PERMUTE([1..n])   // generate a random permutation of indices
2  for i = 1 to n
3      if A[pi[i]] == x
4          return pi[i]            // found x
5  return NOT_FOUND

(d) Expected running time of Randomized-Search:

For any fixed array with exactly copies of , the random permutation places the occurrences at uniformly random positions within the permutation order. Let be the position of the first occurrence of in the permuted order.

Using indicator variables: let . Then:

By a cleaner argument: the first occurrence of in a random permutation of elements, of which are “hits”, has expected position .

This holds for any fixed input, since randomness comes from the permutation, not the input.

(e) Comparison:

When is Modular-Search slow? An adversary who knows the step can arrange the copies of at the last positions in the modular order, forcing comparisons regardless of .

How does randomization help? Randomized-Search generates a new random permutation for each run. Even if an adversary knows the algorithm, they cannot predict the permutation, so they cannot arrange the data to force the worst case. For any fixed input with copies of , the expected time is — proportionally faster for larger , and only when .

Answer: Modular-Search has worst-case (controllable by an adversary); Randomized-Search has expected time against any fixed input.

4.4. Determining Uniform Distributions (Lecture 7, Example 1)

For each of the following, determine whether the probability distribution is uniform:

(a) Rolling a fair six-sided die.

(b) Rolling two fair six-sided dice and looking at the sum of the faces.

(c) Choosing a random student ID from a class of students.

Click to see the solution

(a) Rolling a fair six-sided die:

The sample space is . Each face has probability , so each outcome is equally likely.

Uniform? Yes.

(b) Sum of two fair dice:

The sample space for individual rolls is (36 equally likely pairs). But if we look at the sum, the sample space is , and these values are not equally likely. For instance:

• Sum = 2 occurs only 1 way: — probability
• Sum = 7 occurs 6 ways: — probability

Uniform? No.

(c) Choosing a random student ID:

By default, “choosing at random” means uniformly at random. Each of the student IDs has probability .

Uniform? Yes (by convention).

4.5. Dependent Random Variables (Lecture 7, Example 2)

Give an example of two random variables that are not independent.

Click to see the solution

Key Concept: Two variables are dependent if knowing the value of one changes the probability distribution of the other.

Let be the sample space of a single fair coin toss. Define:

Then:

• and

But .

Since the joint probability does not equal the product of the individual probabilities, and are dependent. Intuitively: if (heads), then must be 0 — knowing tells you exactly what is.

Answer: and on a single coin toss are not independent.

4.6. Expected Number of Heads (Lecture 7, Example 3)

When tossing a fair coin times, what is the expected number of heads?

Click to see the solution

Key Concept: Decompose the count into indicator variables and use linearity of expectation.

1. Define indicator variables: For each toss , let:
2. Express total heads: The total number of heads is .
3. Apply linearity of expectation and the indicator lemma:

Answer: The expected number of heads in tosses is .

4.7. Probabilistic Analysis of the Hiring Problem (Lecture 7, Example 4)

When evaluating candidates (each arriving in a uniformly random order), what is the expected number of times we hire (replace) an agent?

Click to see the solution

Key Concept: Use indicator variables. The -th candidate is hired if and only if they are the best among the first candidates.

1. Define indicator variables: For each , let:

2. Compute probabilities: The -th candidate is hired iff they are the best of . Since the order is uniformly random, each of the first candidates is equally likely to be the best:

3. Expected total hires:

   Concretely: the 1st candidate is always hired (), the 2nd with probability , the 3rd with probability , and so on.

Answer: The expected number of hires is , much less than the worst-case .

4.8. Expected Score in a Coin Game (Lecture 7, Task 1)

Consider a game in which we toss a pair of coins. For each heads you gain 3 points, and for each tails you lose 2 points. What is the expected value of your score?

Click to see the solution

Key Concept: Define a random variable over the sample space, compute .

1. Define the sample space: Assuming a fair coin, each outcome has probability .
2. Define the score random variable :
   • (two heads)
   • (one head, one tail)
   • (one head, one tail)
   • (two tails)
3. Compute the expected value:

Answer: The expected score is point.

4.9. Expected Height of a Randomly Chosen BST (Lecture 7, Task 2)

What is the expected height of a randomly chosen binary search tree?

(a) With 5 nodes.

(b) With nodes (general formula).

Click to see the solution

Key Concept: A randomly chosen BST means we pick uniformly at random among all valid BST shapes (not among all insertion orders). The number of distinct BST shapes on nodes is the -th Catalan number .

(a) For :

Step 1 — Count the shapes. The number of BST shapes on 5 nodes is:

The lecture scratchpad verifies this by grouping shapes by root value. For a BST on keys , if key is the root, then the left subtree has nodes ( shapes) and the right subtree has nodes ( shapes):

Root	Left shapes	Right shapes	Subtotal
1			14
2			5
3			4
4			5
5			14
Total			42

Step 2 — Heights. For nodes, heights range from 2 (minimum: a nearly complete tree) to 4 (maximum: a linear chain). Computing the exact expected height requires enumerating all 42 shapes, which is done computationally. The expected height is approximately 2.7 for .

(b) For general :

A uniformly random BST shape (one of shapes chosen uniformly) corresponds to a random binary plane tree. It is known from combinatorics that the expected height of such a tree grows as .

This is significantly worse than the expected height of a randomly built BST (from a random insertion order). The key insight: the uniform distribution over shapes is not the same as the uniform distribution over insertion orders, and the two give very different height behavior.

Answer: For : shapes, heights 2–4, expected height . For general : expected height .

4.10. Expected Height of a Randomly Built BST (Lecture 7, Task 3)

What is the expected height of a randomly built binary search tree obtained by inserting keys one by one into an initially empty tree?

(a) 5 keys.

(b) keys (general formula).

Click to see the solution

Key Concept: A randomly built BST inserts keys in a uniformly random permutation order — each of the orderings is equally likely. The resulting height depends heavily on which key becomes the root (and then the sub-roots recursively).

Lecture worked example (): The professor enumerated all permutations of to illustrate the method. The result is:

because 16 permutations yield trees of height 2 and 8 permutations yield trees of height 3.

(a) For :

There are permutations of . The same enumeration approach applies (greatly aided by a computer). The key groups are:

• The first key inserted becomes the root. If it is 1 or 5, the tree immediately degenerates to a chain on one side.
• Middle root values (2, 3, or 4) create a more balanced split.

The expected height for is approximately (between 2 and 4), computed by enumerating and averaging over all 120 permutations.

(b) For general :

It is proven (Cormen et al. 2022, §12.4) that the expected height of a randomly built BST on nodes is .

The intuition: in a random permutation, the root is equally likely to be any of the keys. Once the root is chosen, the left and right subtrees are themselves randomly built BSTs of expected sizes close to each (on average), leading to a balanced recursive structure and thus height.

Answer: For : expected height (computed by enumeration). For general : expected height .